package org.basis.algorithm.recursion;

/**
 * n皇后问题
 *
 * @author Mr_wenpan@163.com 2021/12/29 21:48
 */
public class NQueens {

    public static void main(String[] args) {
        int i = nQueen(4);
        System.out.println(i);
    }

    /**
     * n皇后问题
     */
    public static int nQueen(int num) {
        int[] record = new int[num];
        for (int i = 0; i < num; i++) {
            record[i] = -1;
        }
        return process(num, record, 0);
    }

    /**
     * 几皇后问题
     *
     * @param num    即皇后问题
     * @param record 表示第i行的皇后放在哪个位置，比如record[0] = 2 表示第0行的皇后放在下标为2的位置
     * @param i      第i行
     * @return int 总共有多少个解
     */
    public static int process(int num, int[] record, int i) {
        // 成功走到最后一行下面，则返回一种解法
        if (i == num) {
            return 1;
        }
        int res = 0;
        // 从头试到尾
        for (int j = 0; j < num; j++) {
            // 判断皇后放这里是否合法
            if (isValid(record, i, j)) {
                // 如果合法，则放在这里
                record[i] = j;
                // 继续放下一行的皇后
                res += process(num, record, i + 1);
                record[i] = -1;
            }
        }
        return res;
    }

    /**
     * 第i行的皇后放第j列是否合法
     */
    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            // 因为我们是以行维度来放置皇后的，所以每行的皇后一定不共行，只用检查他们是否共列或共斜线即可
            // 共斜线：斜率相等则一定共斜线（x1 - x2 == y1 - y2）
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

}
